package com.yequan.leetcode.array.numberOfSubarrays_1248;

/**
 * //给你一个整数数组 nums 和一个整数 k。
 * //
 * // 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
 * //
 * // 请返回这个数组中「优美子数组」的数目。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * // 输入：nums = [1,1,2,1,1], k = 3
 * //输出：2
 * //解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
 * //
 * //
 * // 示例 2：
 * //
 * // 输入：nums = [2,4,6], k = 1
 * //输出：0
 * //解释：数列中不包含任何奇数，所以不存在优美子数组。
 * //
 * //
 * // 示例 3：
 * //
 * // 输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
 * //输出：16
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 50000
 * // 1 <= nums[i] <= 10^5
 * // 1 <= k <= nums.length
 * //
 * // Related Topics 双指针
 *
 * @author : Administrator
 * @date : 2020/4/21
 */
public class NumberOfSubarrays {

    /**
     * 双指针
     * 使用left,right来统计数组中的奇数个数
     * right指针先走,当碰到奇数时,oddCnt+1,当oddCnt==k时,右指针往后探测,找到第一个奇数,记录位置,此时右区间长度为 right,
     * 左指针开始探测,直至第一个奇数此时区间长度为 leftCnt
     * 此时 优美子集个数为 (leftCnt+1)*(rightCnt+1)
     * 如此进入下一个区间
     *
     * @param nums
     * @param k
     * @return
     */
    public int numberOfSubarrays(int[] nums, int k) {
        int left = 0, right = 0, oddCnt = 0, ans = 0;
        while (right < nums.length) {
            oddCnt += (nums[right++] & 1);
            if (oddCnt == k) {
                int lastRight = right;
                //右指针向右探测,直到第一个奇数出现
                while (right < nums.length && (nums[right] & 1) == 0) {
                    right++;
                }
                int rightEventCnt = right - lastRight;
                //左指针向右探测,直到第一个奇数出现
                int leftEvenCnt = 0;
                while ((nums[left] & 1) == 0) {
                    leftEvenCnt++;
                    left++;
                }
                //当前区间内存在的优美子集个数
                ans += (leftEvenCnt + 1) * (rightEventCnt + 1);
                left++;
                oddCnt--;
            }
        }
        return ans;
    }

}
